package hotLeetcode;

public class H416Leetcode {
    public static boolean canPartition(int[] nums) {


        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 如果和是奇数，不可能分成两个相等的子集
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            // 逆序遍历，确保每个数只被选取一次
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];



    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(canPartition(nums));

    }
}
